package top.wfzzq.ds.sort;

/**
 * 快速排序
 * 
 * @author wanghui
 *
 */
public class QuickSort {
	public static void sort(int[] array) {
		// 开始查找的数据是整个数组
		sort(array, 0, array.length - 1);
	}

	public static void sort(int[] array, int start, int end) {
		// 递归要点，停止条件，查找的区间必须合法
		if (start > end) {
			return;
		}
		// 6 1 2 7 9 3 4 5 10 8
		// start=0 end=9 base=6 i=0 j=9

		// 定义查找相关变量
		int i, j;
		// 基准数
		int base;
		// 交换位置的临时变量
		int temp;
		// 挑选基准数为第一个数
		base = array[start];
		i = start;
		j = end;
		// 当i<j的时候都会继承
		while (i < j) {
			while (base <= array[j] && i < j) {
				j--;
			}
			while (base >= array[i] && i < j) {
				i++;
			}
			// 如果找到le合适数就交换位置
			if (i < j) {
				temp = array[i];
				array[i] = array[i];
				array[j] = temp;
			}
		}
		// 右边开始找小于基准数的数所在位置
		// j array[j] base
		// 9 8 6
		// 8 10 6
		// 7 5 6

		// 左边开始找大于基准数的数所在位置
		// i array[i] base
		// 0 6 6
		// 1 1 6
		// 2 2 6
		// 3 7 6
		// 第一輪
		// 6 1 2 7 9 3 4 5 10 8
		// 6 1 2 5 9 3 4 7 10 8
		// 第二輪
		// 6 1 2 7 9 3 4 5 10 8
		// j=5
		// i=4
		// i=5
		// 3 1 2 5 4 6 9 7 10 8

		// 将基准数放到i的位置（这个时候i前面的都比基准数小，后面的都大）
		array[start] = array[i];
		array[i] = base;
		// 递归必须调用自己
		// 处理左半区
		sort(array, start, i - 1);
		// 处理右半区
		sort(array, i + 1, end);
	}
}
